#include <iostream>
#include "../head/Edge.h"
#include "../head/ReadGraph.h"
// #include "../head/IndexMinHeap.h"
#include "../head/DenseGraph.h"
#include "../head/SparseGraph.h"
#include "../head/BellmanFord.h"
#include "../head/Dijkstra.h"

void testDijkstra();
void testBellmanFord();

int main() {
	// testDijkstra();
	testBellmanFord();
    return 0;
}

// 测试 Dijkstra 从原点 s 到其他所有点的最短路径
void testDijkstra(){
    string filename = "testG1.txt";
    int V = 5;

    // SparseGraph<int> g = SparseGraph<int>(V, true);		// 有向图
	// 无向图相当于保存了有向图的两条边，其方向是相反的
    SparseGraph<int> g = SparseGraph<int>(V, false);	// 无向图
    ReadGraph<SparseGraph<int>, int> readGraph(g, filename);

    cout<<"Test Dijkstra:"<<endl<<endl;
    Dijkstra<SparseGraph<int>, int> dij(g,0);
    for( int i = 1 ; i < V ; i ++ ){
        cout<<"Shortest Path to "<<i<<" : "<<dij.shortestPathTo(i)<<endl;
        dij.showPath(i);
        cout<<"----------"<<endl;
    }
}


// 测试 Bellmanford 从原点 s 到其他所有点的最短路径
void testBellmanFord(){
    string filename = "testG2.txt";
    //string filename = "testG_negative_circle.txt";
    int V = 5;

    SparseGraph<int> g = SparseGraph<int>(V, true);
    ReadGraph<SparseGraph<int>, int> readGraph(g, filename);

    cout<<"Test Bellman-Ford:"<<endl<<endl;
    BellmanFord<SparseGraph<int>, int> bellmanFord(g,0);
    if( bellmanFord.negativeCycle() )
        cout<<"The graph contain negative cycle!"<<endl;
    else
        for( int i = 1 ; i < V ; i ++ ){
            cout<<"Shortest Path to "<<i<<" : "<<bellmanFord.shortestPathTo(i)<<endl;
            bellmanFord.showPath(i);
            cout<<"----------"<<endl;
        }
}
